#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-12-01 10:52 上午
# @Author  : yangdy
# @File    : 33. 搜索旋转排序数组
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        u = 1
        while u < len(nums) and nums[u-1] < nums[u]:
            u += 1
        import bisect
        x = bisect.bisect_left(nums[:u], target)
        if 0 <= x < u and nums[x] == target:
            return x
        x = bisect.bisect_left(nums[u:], target)
        if 0 <= x < len(nums) - u and nums[x+u] == target:
            return x+u
        return -1


questions = [
    ([4, 5, 6, 7, 0, 1, 2], 0),
]

work(questions, lambda q: Solution().search(q[0], q[1]))
